package com.链表2.双链表;

 class ListNode{
    int val;
    ListNode next; //下节点
    ListNode prev; //上节点
    ListNode(int val){
        this.val = val;
    }

}


public class MyLinkedList {
    /** Initialize your data structure here. */
    int size  ;
    ListNode head,tail; //哨兵节点
    public MyLinkedList() {
        this.head = new ListNode(0);
        this.tail = new ListNode(0);
        this.size = 0;
        head.next = tail;
        tail.prev = head;
    }

    /** 获取链表中第 index 个节点的值。如果索引无效，则返回-1 */
    public int get(int index) {
        if(index < 0 || index >= size){
            return -1;
        }
        ListNode cur = head;
        //判断从哪边遍历快
        if(index + 1 < size - index){
           for(int i = 0 ;i<index+1;i++){
               cur = cur.next;
           }
        }
        else{
            cur = tail;
            for(int i = 0;i<size-index;i++){
                cur = cur.prev;
            }
        }

        return  cur.val;




    }

    /** 在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。*/
    public void addAtHead(int val) {
        size++;
        ListNode cur = head,down = head.next;
        ListNode add = new ListNode(val);
        add.prev = cur;
        add.next = down;
        cur.next = add;
        down.prev = add;

    }

    /** 将值为 val 的节点追加到链表的最后一个元素。 */
    public void addAtTail(int val) {
        size++;
        ListNode cur = tail,up = tail.prev;
        ListNode add = new ListNode(val);
        add.next = cur;
        add.prev = up;
        cur.prev = add;
        up.next = add;
    }

    /**
     * 在链表中的第 index 个节点之前添加值为 val  的节点。
     * 如果 index 等于链表的长度，则该节点将附加到链表的末尾。
     * 如果 index 大于链表长度，则不会插入节点。
     * 如果index小于0，则在头部插入节点。
     * @param index
     * @param val
     */
    public void addAtIndex(int index, int val) {
        if(index > size){
            return;
        }
        if(index < 0){
            index = 0;
        }
        size ++ ;
        ListNode up = null,down = null;
        //从头插入较快
        //如果 index 等于链表的长度，则该节点将附加到链表的末尾。
        // 在链表中的第 index 个节点之前添加值为 val  的节点
        if(index < size - index){
            up = head;
            for(int i  = 0 ;i<index;i++){
              up  = up.next;
            }
            down = up.next;
        }
        //从尾部插入比较快
        else{
            down = tail;
            for(int i = 0;i<size-index-1;i++){
                down  = down.prev;
            }
            up = down.prev;
        }

        ListNode add = new ListNode(val);
        add.next = down;
        add.prev = up;
        up.next = add;
        down.prev = add;






    }

    /** 如果索引 index 有效，则删除链表中的第 index 个节点 */
    public void deleteAtIndex(int index) {
        if(index < 0 || index >= size){
            return;
        }
        size--;
        ListNode up = null,down = null;
        //从头遍历
        if(index  < size - index){
            up = head;
            for(int i  =  0 ;i<index;++i){
                up = up.next;
            }
            down = up.next.next;
        }
        //从尾遍历
        else{
            down = tail;
            for(int i = 0 ;i < size-index;++i){
                down = down.prev;
            }
            up = down.prev.prev;
        }
        up.next = down;
        down.prev = up;

    }
    public String toString(){
        StringBuilder builder = new StringBuilder();
        builder.append(String.format("容量：%s,双链表{",this.size));
        ListNode cur = head;
        while (cur != null){

            String prev = "",next = "";
            if(cur.next != null){
                next = String.valueOf( cur.next.val);
            }
            if(cur.prev != null){
                prev = String.valueOf( cur.prev.val);
            }
           builder.append( String.format("[cur:%s,prev:%s,next:%s]",cur.val,prev,next));
            if(cur.next != null){
                builder.append("->");
            }
            cur = cur.next;
        }
            builder.append("}");
        return builder.toString();
    }


    public static void main(String[] args) {
        MyLinkedList link = new MyLinkedList();
        link.addAtHead(5);
        link.addAtIndex(1,2);
        System.out.println(link.get(1));
        System.out.println(link.toString());
        link.addAtHead(6);
        link.addAtTail(2);
        System.out.println(link.toString());
        System.out.println(link.get(3));
        link.addAtTail(1);
        System.out.println(link.get(5));
        System.out.println(link.toString());
        link.addAtHead(2);
        System.out.println(link.toString());
        System.out.println(link.get(2));
        link.addAtHead(6);



    }
}
